//
// Created by chen on 2025/1/19.
//
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//顺序表结构
typedef struct vector {
    int size, count;
    int *data;
} vector;

/**
 *  创建一个新的顺序表（vector），并对其进行初始化

动态分配内存：
malloc(sizeof(vector))：为 vector 结构体分配内存，返回一个指向该内存的指针 p。
malloc(sizeof(int) * n)：为顺序表的数据部分（data）分配内存，大小为 n 个 int 类型的空间。

初始化顺序表：
p->size = n：设置顺序表的最大容量为 n。
p->count = 0：初始化顺序表的当前元素个数为 0，表示顺序表为空。
p->data：将分配的内存地址赋值给 data，用于存储顺序表中的元素。
返回顺序表指针：
函数返回指向新创建的顺序表的指针 p，供后续使用。
 *
 * */
vector *getNewVector(int n) {
    vector *p = (vector *)malloc(sizeof(vector));
    p->size = n;
    p->count = 0;
    p->data = (int *)malloc(sizeof(int) * n);
    return p;
}

//扩容
int expand(vector *v) {
    if (v == NULL) return 0;
    printf("expand v from %d to %d\n", v->size, 2 * v->size);
    int *p = (int *)realloc(v->data, sizeof(int) * 2 * v->size);
    if (p == NULL) return 0; // 扩容失败，保持原样
    v->data = p;
    v->size *= 2;
    return 1;
}

//插入
/**
 * 数组进行逆序遍历
 * @param{ *v 顺序表}
 * pos 给哪个位置插入
 * value 值
 * */
int insert(vector *v, int pos, int value) {
    // 要插入的位置<0 或者大于总个数
    if (pos < 0 || pos > v->count) return 0;
    // 满了 并且扩容失败的话
    if (v->size == v->count && !expand(v)) return 0;
    for (int i = v->count - 1; i >= pos; i--) {
        // [1,2,3,6] 在1-2的之间位置插入5,则2，3，6都往后移动一位
        v->data[i + 1] = v->data[i];
    }
    v->data[pos] = value;
    v->count += 1;
    return 1;
}

//删除
int erase(vector *v, int pos) {
    // [1,2,3,6] 删除2 传入索引1 从3,6都往前移动一位
    if (pos < 0 || pos >= v->count) return 0; // 检查 pos 是否合法
    for (int i = pos + 1; i < v->count; i++) {
        v->data[i - 1] = v->data[i]; // 相当于把原本val为2的地方重新赋值
    }
    v->count -= 1;
    return 1;
}

//输出顺序表
void output_vector(vector *v) {
    int len = 0;
    for (int i = 0; i < v->size; i++) {
        len += printf("%3d", i);
    }
    printf("\n");
    for (int i = 0; i < len; i++) printf("-");
    printf("\n");
    for (int i = 0; i < v->count; i++) {
        printf("%3d", v->data[i]);
    }
    printf("\n");
    printf("\n\n");
    return;
}

//释放顺序表
void clear(vector *v) {
    if (v == NULL) return;
    free(v->data);
    free(v);
    return;
}

int main() {
    srand(time(0));
#define MAX_OP 20

    vector *v = getNewVector(2);
    for (int i = 0; i < MAX_OP; i++) {
        int op = rand() % 4, pos, val, ret;
        switch (op) {
            case 0:
            case 1:
            case 2:
                pos = rand() % (v->count + 2);
                val = rand() % 100;
                ret = insert(v, pos, val);
                printf("insert %d at %d to vector = %d\n", val, pos, ret);
                break;
            case 3:
                pos = rand() % (v->count + 2);
                ret = erase(v, pos);
                printf("erase item at %d in vector = %d\n", pos, ret);
                break;
        }
        output_vector(v);
    }
    clear(v);
    return 0;
}